//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE
csFastList<T,PoolGrowStep>::csFastList()
:m_size(0)
,m_freeNodes(csFASTLIST_DEFAULT_POOL)
{
	_init(csFASTLIST_DEFAULT_POOL);
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE
csFastList<T,PoolGrowStep>::csFastList(s32 capacity)
:m_size(0)
,m_freeNodes(capacity)
{
	_init(capacity);
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE
csFastList<T,PoolGrowStep>::csFastList(const csFastList<T,PoolGrowStep>& list)
:m_freeNodes(list.size())
{
	_init(list.size());
	_assign(list.begin(),list.end());
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE
csFastList<T,PoolGrowStep>::~csFastList()
{
	clear();
	_destroy();
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE void
csFastList<T,PoolGrowStep>::operator =(const csFastList<T,PoolGrowStep>& rhs)
{
	clear();
	_assign(rhs.begin(),rhs.end());
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> bool
csFastList<T,PoolGrowStep>::operator ==(const csFastList<T,PoolGrowStep>& rhs) const
{
	if(size()!=rhs.size())
	{
		return false;
	}
	const_iterator lit		= begin();
	const_iterator rit		= rhs.begin();
	const_iterator liend	= end();
	const_iterator riend	= rhs.end();
	while(lit!=liend&&rit!=riend)
	{
		if((*lit)!=(*rit))
		{
			return false;
		}
		++lit;
		++rit;
	}
	return true;
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE bool
csFastList<T,PoolGrowStep>::operator !=(const csFastList<T,PoolGrowStep>& rhs) const
{
	return !((*this)==rhs);
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE T&
csFastList<T,PoolGrowStep>::front()
{
	csASSERT(m_head!=m_head->m_next);
	return m_head->m_next->m_data;
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE const T&
csFastList<T,PoolGrowStep>::front() const
{
	csASSERT(m_head!=m_head->m_next);
	return m_head->m_next->m_data;
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE T&
csFastList<T,PoolGrowStep>::back()
{
	csASSERT(m_head!=m_head->m_prev);
	return m_head->m_prev->m_data;
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE const T&
csFastList<T,PoolGrowStep>::back() const
{
	csASSERT(m_head!=m_head->m_prev);
	return m_head->m_prev->m_data;
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE void
csFastList<T,PoolGrowStep>::push_back(const T& val)
{
	insert(end(),val);
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE void
csFastList<T,PoolGrowStep>::pop_back()
{
	csASSERT(m_size>0);
	iterator it(end());
	--it;
	remove(it);
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE void
csFastList<T,PoolGrowStep>::push_front(const T& val)
{
	insert(begin(),val);
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE void
csFastList<T,PoolGrowStep>::pop_front()
{
	csASSERT(m_size>0);
	remove(begin());
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE  typename csFastList<T,PoolGrowStep>::iterator
csFastList<T,PoolGrowStep>::begin()
{
	return iterator(m_head->m_next);
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE typename csFastList<T,PoolGrowStep>::const_iterator
csFastList<T,PoolGrowStep>::begin() const
{
	return const_iterator(m_head->m_next);
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE typename csFastList<T,PoolGrowStep>::iterator
csFastList<T,PoolGrowStep>::end()
{
	return iterator(m_head);
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE typename csFastList<T,PoolGrowStep>::const_iterator
csFastList<T,PoolGrowStep>::end() const
{
	return const_iterator(m_head);
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE typename csFastList<T,PoolGrowStep>::reverse_iterator
csFastList<T,PoolGrowStep>::rbegin()
{
	return reverse_iterator(m_head->m_prev);
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE typename csFastList<T,PoolGrowStep>::const_reverse_iterator
csFastList<T,PoolGrowStep>::rbegin() const
{
	return const_reverse_iterator(m_head->m_prev);
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE typename csFastList<T,PoolGrowStep>::reverse_iterator
csFastList<T,PoolGrowStep>::rend()
{
	return reverse_iterator(m_head);
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE typename csFastList<T,PoolGrowStep>::const_reverse_iterator
csFastList<T,PoolGrowStep>::rend() const
{
	return const_reverse_iterator(m_head);
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE typename csFastList<T,PoolGrowStep>::iterator
csFastList<T,PoolGrowStep>::insert(typename csFastList<T,PoolGrowStep>::iterator where, const T& val)
{
	Node* node		= _alloc_node(val);
	node->m_next	= where.m_node;
	node->m_prev	= where.m_node->m_prev;
	node->m_next->m_prev	= node;
	node->m_prev->m_next	= node;
	++m_size;
	return iterator(node);
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE void
csFastList<T,PoolGrowStep>::remove(typename csFastList<T,PoolGrowStep>::iterator where)
{
	csASSERT(where.m_node&&where!=end());
	Node* node	= where.m_node;
	node->m_prev->m_next	= node->m_next;
	node->m_next->m_prev	= node->m_prev;
	_free_node(node);
	--m_size;
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE typename csFastList<T,PoolGrowStep>::iterator
csFastList<T,PoolGrowStep>::remove_return_next(typename csFastList<T,PoolGrowStep>::iterator where)
{
	csASSERT(where.m_node&&where!=end());
	iterator cur(where.m_node->m_next);
	remove(where);
	return cur;
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE void
csFastList<T,PoolGrowStep>::remove(const T& val)
{
	iterator it(find(val));
	while(it!=end())
	{
		iterator tit = it;
		it = find(val,it);
		remove(tit);
	}
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE typename csFastList<T,PoolGrowStep>::iterator 
csFastList<T,PoolGrowStep>::find(const T& val)
{
	return find(val,end());
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE typename csFastList<T,PoolGrowStep>::const_iterator
csFastList<T,PoolGrowStep>::find(const T& val) const
{
	return find(val,end());
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE typename csFastList<T,PoolGrowStep>::iterator 
csFastList<T,PoolGrowStep>::find(const T& val, typename csFastList<T,PoolGrowStep>::iterator it)
{
	++it;
	iterator iend = end();
	while(it!=iend)
	{
		if(it.m_node->m_data==val)
		{
			return it;
		}
		++it;
	}
	return end();
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE typename csFastList<T,PoolGrowStep>::const_iterator
csFastList<T,PoolGrowStep>::find(const T& val, typename csFastList<T,PoolGrowStep>::const_iterator it) const
{
	++it;
	const_iterator iend = end();
	while(it!=iend)
	{
		if(it.m_node->m_data==val)
		{
			return it;
		}
		++it;
	}
	return end();
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE bool
csFastList<T,PoolGrowStep>::empty() const
{
	return 0==m_size;
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE s32
csFastList<T,PoolGrowStep>::size() const
{
	return m_size;
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE void
csFastList<T,PoolGrowStep>::clear()
{
	iterator it = begin();
	iterator iend= end();
	while(it!=iend)
	{
		it = remove_return_next(it);
	}
	m_size = 0;
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE void
csFastList<T,PoolGrowStep>::trim()
{
	m_freeNodes.trim();
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE void
csFastList<T,PoolGrowStep>::swap(csFastList<T,PoolGrowStep>& rhs)
{
	csSwap<s32>(m_size,rhs.m_size);
	csSwap<Node*>(m_head,rhs.m_head);
	m_freeNodes.swap(rhs.m_freeNodes);
	m_memoryBlocks.swap(rhs.m_memoryBlocks);
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE void
csFastList<T,PoolGrowStep>::to_array(T** outArray) const
{
	csASSERT(csNULL!=outArray);
	const_iterator it	= begin();
	const_iterator iend	= end();
	s32	i				= 0;
	while(it!=iend)
	{
		(*outArray)[i] = *it;
		++it;
		++i;
	}
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE void
csFastList<T,PoolGrowStep>::_init(s32 capacity)
{
	if(capacity<1)
	{
		capacity = csFASTLIST_DEFAULT_POOL;
	}
	Node* addressBase = static_cast<Node*>(malloc(capacity*sizeof(Node)));
	MemoryBlock block(addressBase,capacity);
	m_memoryBlocks.push_back(block);
	for(s32 i=0;i<capacity-1;i++)
	{
		m_freeNodes.push_back(addressBase+i);
	}
	m_head = new(addressBase+capacity-1) Node();
	m_head->m_next = m_head;
	m_head->m_prev = m_head;
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> void
csFastList<T,PoolGrowStep>::_destroy()
{
	for(s32 i=0;i<m_memoryBlocks.size();i++)
	{
		free(m_memoryBlocks[i].m_memoryBlockPtr);
	}
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> void
csFastList<T,PoolGrowStep>::_assign(typename csFastList<T,PoolGrowStep>::const_iterator beginNode, typename csFastList<T,PoolGrowStep>::const_iterator endNode)
{
	clear();
	for(const_iterator it=beginNode;it!=endNode;++it)
	{
		push_back(it.m_node->m_data);
	}
};

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE typename csFastList<T,PoolGrowStep>::Node*
csFastList<T,PoolGrowStep>::_alloc_node(const T& val)
{
	if(m_freeNodes.empty())
	{
		Node* addressBase	= static_cast<Node*>(malloc(PoolGrowStep*sizeof(Node)));
		MemoryBlock block(addressBase,PoolGrowStep);
		m_memoryBlocks.push_back(block);
		for(s32 i=0;i<PoolGrowStep;i++)
		{
			m_freeNodes.push_back(addressBase+i);
		}
	}
	void* addr = m_freeNodes.back();
	m_freeNodes.pop_back();
	return new(addr) Node(val);
}

//------------------------------------------------------------------------
template<typename T, s32 PoolGrowStep> csINLINE void
csFastList<T,PoolGrowStep>::_free_node(typename csFastList<T,PoolGrowStep>::Node* node)
{
	node->~Node();
	m_freeNodes.push_back(node);
}